package lc;
import org.junit.*;
public class Ex130 {

    @Test
    public void test() {
        Solution s = new Solution();
        char[][] board = {{'X','O','X'}, {'O','X','O'}, {'X','O','X'}};   
        s.solve(board);
    }

    class Solution {
        char[][] board;
        int m, n;
        public void solve(char[][] board) {
            this.board = board;
            this.m = board.length;
            this.n = board[0].length;
            for (int i = 0; i < n; i++) {
                if (board[0][i] == 'O') {
                    dfs(0, i);
                }
                if (board[m - 1][i] == 'O') {
                    dfs(m - 1, i);
                }
            }
            for (int i = 0; i < m; i++) {
                if (board[i][0] == 'O') {
                    dfs(i, 0);
                }
                if (board[i][n - 1] == 'O') {
                    dfs(i, n - 1);
                }
            }

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                }
            }

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == '#') {
                        board[i][j] = 'O';
                    }
                }
            }
        }
    
        //将边界的X变成#
        private void dfs(int i, int j) {
            if (!isValid(i, j) || board[i][j] != 'O') {
                return;
            }
            board[i][j] = '#';
            dfs(i - 1, j);
            dfs(i + 1, j);
            dfs(i, j + 1);
            dfs(i, j - 1);
        }

        private boolean isValid(int i, int j) {
            return i >= 0 && i < m && j >= 0 && j < n;
        }
    }
}
